The Invention relates to the field of digital integrated circuits, and in particular relates to the design of static CMOS Content-Addressable Memory (CAM) arrays. CAM arrays are a form of associative memory. In particular, the invention relates to cells and CAM arrays having bit cells capable of storing three or more content states including: xe2x80x9clogic onexe2x80x9d, xe2x80x9clogic zeroxe2x80x9d, and at least one form of xe2x80x9cdon""t carexe2x80x9d; such CAM arrays are known as ternary CAMs.
CMOS CAM arrays are commonly used in cache systems, and other address translation systems, of high speed computing systems. They are also useful in high-speed network routers, and many other applications known in the art of computing.
CAM arrays are characterized by circuitry capable of generating a xe2x80x9cmatchxe2x80x9d output indicating whether any location of the array contains a data pattern matching a query input, and the identity of that location. CAM arrays typically are comprised of multiple rows, each row having multiple cells. Each cell of the array typically has the ability to store a unit of data, and the ability to compare that unit of data with a unit of a query input. Compare result indications of cells of each row are combined to produce a xe2x80x9cmatchxe2x80x9d signal for the row. Match signals from each row of the multiple rows together constitute the match output of the array; these signals may be encoded or used to select data from rows of additional memory.
Cells of a row typically are also connected to a common write line. The common write line allows enabling of simultaneous data writing to each cell of the row from a set of data input, or data input-output, lines.
Each cell of a CAM array is located within a column of cells of the array. Cells of a column are connected to a common unit of the query input, and are typically also connected to a common set of data input lines for writing data to cells of the array. Writing of a cell of the array typically requires that the data input lines for the cell""s column be driven to a desired data value while the write line for the cell""s row is activated. The data input lines may or may not be common with the query input lines of a cell depending upon the cell design used.
The unit of data stored in a CAM array is often binary, having two possible content states: logic one, and logic zero. Cells of these arrays produce a match compare result if the query input is equal to the data stored in the cell, and a mismatch result otherwise. CAM arrays are known that can store three or more states: logic one, logic zero, and don""t care. Cells of these xe2x80x9cternary CAMxe2x80x9d arrays produce a match compare result if the query input is either equal to the data stored in the cell, or the cell contains a don""t care state, and a mismatch result otherwise.
Ternary CAM can be implemented with cells storing two binary bits, comprising a data bit and a mask bit, in memory elements of the cell. Two binary bits gives four possible states per cell: logic one, logic zero, and two possible don""t-care states don""t-care-one, and don""t-care-zero. Binary and three-state (or ternary) static CMOS CAM cells of this type have been described in U.S. Pat. No. 6,044,005, the disclosure of which is hereby incorporated herein by reference.
Ternary CAM arrays are particularly useful in address translation systems that allow variably sized allocation units. Ternary CAM arrays are particularly useful for storing routing tables of network routers and switches.
Network routers typically receive, and retransmit, packets (packets are also known as frames in the context of Fibre Channel networks) having destination address fields of width 32 to 64 bits. Routers typically extract these address fields and use them to determine the appropriate port for retransmission. Determination of the appropriate port is typically performed by looking up the destination address in a routing table.
It is often impractical to allocate sufficient RAM memory to a routing table to permit accessing the table by using the destination address as a RAM address; ternary CAM can be used to construct a routing table having much less memory than would be required if the entire destination address were used as a RAM address. Ternary CAM is particularly useful in constructing fast routing tables for use in routing packets according to the TCP-IP and Fibre-Channel protocols.
CAM cells may store their data in either dynamic or static storage cells as known in the art of memory circuitry. Static storage offers the advantage that refresh circuitry is not required, and the advantage that true and complement signals may be drawn from each storage cell. Ternary Static CMOS CAM cells are known, including those illustrated in U.S. Pat. No. 6,044,005, that utilize a pair of six-transistor CMOS static RAM cells as memory elements for storing a mask bit and a data bit.
It is known that combining compare results of multiple cells of a row can be done in several ways. FIG. 1 (labeled xe2x80x9cprior artxe2x80x9d) of U.S. Pat. No. 6,044,005 illustrates a parallel pulldown configuration, wherein match line ML, connected to all cells of a row, is driven low by device T4 of any cell having a mismatch compare condition. With the parallel pulldown configuration, a match for a row occurs whenever no cell of the row is driving match line ML low. FIG. 6B of U.S. Pat. No. 6,044,005 illustrates a series-string configuration, wherein transmission device T6 couples match line ripple-input ML0 to match line ripple-output ML1 when a match compare condition occurs. The match line ripple-output of each cell (except for the last cell of the row) is connected to the match line ripple-input of a following cell of the row. With this series-string configuration, a match for a row occurs when all cells couple ripple-input to ripple-output. FIG. 8 of U.S. Pat. No. 6,175,514 illustrates a full-complimentary-combiner-gate configuration, wherein compare result signals from each cell are combined by full-complimentary CMOS NAND and NOR gates to generate a row match signal.
The full-complimentary-combiner-gate configuration is fast, but can consume more room on an integrated circuit than may be desirable. The series-string configuration can be slower than desirable. The parallel pulldown configuration can produce mismatch results quickly, but pullup devices required to drive match lines ML of U.S. Pat. No. 6,044,005 FIG. 1 high can consume considerable power.
Operating voltage of modern CMOS integrated circuits is trending downward. There several reasons for this, among them are power conservation and compatibility with newer, submicron, process technology. It has been observed that some existing CAM core cells, including that illustrated in FIG. 1 of U.S. Pat. No. 6,044,005, have single-ended pass circuitry that drops a signal by a threshold voltage prior to driving the gate of a transistor T4 on a critical speed path. As operating voltages decrease, it is advisable to avoid pass gate signal voltage drops on speed-critical devices.
A CAM core cell has been designed capable of storing two binary bits, comprising a data bit and a mask bit. This cell can take on a total of four possible states: logic one, logic zero, and two possible don""t-care states: don""t-care-one, and don""t-care-zero. The cell contains comparison circuitry for detecting match conditions against a query signal, and for pulling down a match line of parallel-pulldown configuration when a mismatch occurs. The comparison circuitry avoids single-ended pass-gate signal voltage drops on speed-critical devices, and avoids crowbar current during transitions of the compare data and compare data complement lines.
An array of the CAM core cells is operated in conjunction with control logic, controlled match line pullups, and query signal driver logic. The control logic controls a precharge signal to the CAM core cell, the controlled match line pullups, and the query signal driver logic to prevent simultaneous conduction of the controlled pullup and match line pulldowns of the cells.
The CAM core cell array has five hundred twelve rows of sixty-eight cells each, and is utilized for a routing table in a network router. It is anticipated that the present invention is applicable to CAM core cell arrays of different dimensions, and for CAM core cell arrays used for other purposes.